# source:https://leetcode.cn/problems/maximum-consecutive-floors-without-special-floors/ 数组
class Solution:
    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
        ans = 0
        special.sort()
        last, final = bottom, top
        for i in range(len(special)):
            if i == 0:
                ans = max(ans, special[i]-last)
            else:
                ans = max(ans, special[i]-special[i-1]-1)
        ans = max(ans, final - special[-1])
        return ans

# source:https://leetcode.cn/problems/minimum-size-subarray-in-infinite-array/ 滑窗
class Solution:
    def minSizeSubarray(self, nums: List[int], target: int) -> int:
        ans = inf
        i, j = 0, 0
        count = 0
        if sum(nums) < target:
            count += sum(nums)*(target // sum(nums))
            j = len(nums)*(target // sum(nums))
        
        while i < len(nums):
            count += nums[j % len(nums)]
            while i < j and count > target:
                count -= nums[i % len(nums)]
                i += 1
            if count == target:
                ans = min(ans, j - i + 1)
            j += 1

        return ans if ans != inf else -1

# source:https://leetcode.cn/problems/maximum-white-tiles-covered-by-a-carpet/description/ 贪心 滑动窗口
import bisect
class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        ans = 0
        tiles.sort(key=lambda x:x[0])
        store = []
        total = [0]
        for _, (m, n) in enumerate(tiles):
            store.append(n)
            total.append(total[-1]+n-m+1)

        for c, t in enumerate(tiles):
            i = t[0]
            j = i + carpetLen - 1
            ind = bisect.bisect_right(store, j)
            cnt = (total[ind] + (j - tiles[ind][0] + 1 if ind < len(tiles) and j >= tiles[ind][0] else 0) - total[c])
            ans = max(ans, cnt)
        return ans